
"""
93.复原 IP 地址
https://leetcode.cn/problems/restore-ip-addresses/

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
"""

from typing import List

class Solution:

    def _if_valid_ip_val(self, strnum: str) -> bool:
        if not strnum:
            return False

        num = int(strnum)
        if num > 255:
            return False
        return True
        
    def find_ip(self, s: str, path:List[str], res:List[str]):
        if len(path)==4 and len(s)==0:
            ip = ".".join(path)
            res.append(ip)
            return

        # 剪枝
        if (len(s) > 3*(4 - len(path))) or (len(s) < 4-len(path)):
            # 剩余的s比需要的数字多，直接return  或者  剩余的s不够组成ip,直接return
            return 

        # 每次只能尝试从s中截取3个数字
        for i in range(1, min(3+1, len(s)+1)): 
            # min(3+1, len(s)+1)防止在第四个数字的时候出现重复
            # 比如，最后剩下35，如果直接设置3+1，会出现两次
            if self._if_valid_ip_val(s[:i]):
                path.append(s[:i])
                self.find_ip(s[i:], path, res)
                path.pop()

        return


    def restoreIpAddresses(self, s: str) -> List[str]:
        """递归+回溯寻找ip"""
        path = []
        res = []
        self.find_ip(s, path, res)
        return res


def test():
    obj = Solution()
    s = "25525511135"
    res = obj.restoreIpAddresses(s)
    print(res)


if __name__ == "__main__":
    test()
